Euclidean Domains
In the previous section we proved that a principal ideal domain possesses the property of unique factorization. Now we are faced with the problem of determining whether or not a given integral domain is a principal ideal domain. This is generally a very difficult question. However, a partial solution is available. Notice that we were able to prove that Z and F[X] are PIDs by using the division algorithm in Z and F[X] respectively. In this section let us introduce a class of integral domains in which an analogue of the division algorithm holds. We will show that every such ring is a PID.
Definition 1: Let R be an integral domain. Then R is called a Euclidean domain if there exists a function :R Z such that
(1) (x) > 0 for all x R.
(2) (x) = 0 if and only if x = 0.
(3) (xy) = (x) (y) for all x,y R.
(4) Let x,y R, y 0. Then there exist q,r R such that x = qy + r, 0 < (r) < (y). (This is a generalization of the division algorithm.)
Example 1: Let R = Z, (x) = |x|. Then conditions (1)-(3) are elementary properties of absolute values. Condition (4) is just the division algorithm in Z.
Example 2: Let R = F[X]. Set (x) = 2deg(x) (x 0), and and = 0 (x = 0). Then (1)-(3) are easy to check. Moreover, by the division algorithm in F[X], given x,y R, y 0, there exist q,r R such that x = qy + r, deg(r) < deg(y). But then 0 < (r) < (y) and condition (4) holds.
Theorem 2: Let R be a Euclidean domain. Then R is a principal ideal domain.
Proof: Let I be a nonzero ideal of R. It suffices to show that I is principal. Let a I be chosen so that a 0 and (a) is a small as possible. We assert that I = (a). It is clear that (a) I. Let x I. Since R is a Euclidean domain, there exist q,t R so that
x = qa + r, 0 <  (r) <  (a).
Note that r = x - qa I If r 0, then (r) < (a), r I, which contradicts the choice of a. Therefore, r = 0 and x = qa (a). Thus I (a).
Let us now give an example of a Euclidean domain which is connected with Fermat's last theorem.
Theorem 3: Let = (-1 + i)/2. Then is a primitive cube root of 1 and Z[ ] is a Euclidean domain.
Before proving Theorem 3, it is necessary to describe Z[ ] more explicitly. Note that 2 + + 1 = 0, so that
Also, 3 = - 2 - , so that
Proceeding by induction, we see that
for all n > 1. Therefore,
Moreover, every element of Z[ ] can be written uniquely in the form a + b , since
a + b  = a' + b'  a - a' = (b' - b) 
 b' - b = 0
 a - a' =0.
And we have proved the following
Lemma 4: Every element of Z[ ] can be uniquely written in the form a + b , a,b Z.
Proof of Theorem 3: If a,b Q, define (a + b ) = (a + b )(a + b ) = a2 - ab + b2, where denotes the complex conjugate of . Since a + b = a + b , we see that (a + b ) = |a + b |2 > 0. Moreover, (a + b ) = 0 a + b = 0. Further, if a,b Z, (a + b ) = a2 - ab + b2 Z. We leave it as an exercise to verify that ( ) = ( ) ( ) for , {a + b | a,b Q}. Let us verify the division algorithm. This is where we use the special properties of . Let x = a + b , y = c + d Z[ ], y 0. Then, in C, we have
where
 , 
belong to Q. There exist integers and such that
|e -  | < 1/2, |f -  | < 1/2.
Set q = +  , r = [(e - ) + (f - ) ]y. Then q Z[ ] and
x = qy + r,
so that r = x - qy Z[ ]. Finally
 (r) =  ((e -  ) + (f -  )  )  (y)
= {(e -  ) 2 - (e -  )(f -  ) + (f -  ) 2}  (y)
< {1/4 + 1/4 + 1/4}  (y)
<  (y).
Corollary 5: If = (-1 + i)/2 is a primitive cube root of 1, then Z[ ] is a unique factorization domain.
|